﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections.Concurrent;
using System.Threading;
using GtsServer.Model;

namespace GtsServer.Service.Index.DAL
{
    public class BinaryIndex<T> where T : IComparable<T>
    {
        public Node<T> root = null;
        private Random rand = new Random();
        private static Object thisLock = new object();
        public void init()
        {

        }
        /// <summary>
        /// 添加节点
        /// </summary>
        /// <param name="key"></param>
        /// <param name="data"></param>
        public void Add(T key, int data)
        {

            Node<T> find = search(root, key);
            if (find == null)
            {
                Node<T> tmp = new_node(key);
                tmp.data.Add(data);
                lock (thisLock)
                {
                    root = insert(root, tmp);
                }
            }
            else
            {
                if (!find.data.Contains(data))
                {
                    find.data.Add(data);
                }
            }
        }
        /// <summary>
        /// 是否存在节点
        /// </summary>
        /// <param name="key"></param>
        /// <param name="data"></param>
        /// <returns></returns>
        public bool IsExist(T key, int data)
        {
            Node<T> find = search(root, key);
            if (find == null)
                return false;
            else
                return find.data.Contains(data);
        }
        /// <summary>
        /// 删除节点
        /// </summary>
        /// <param name="key"></param>
        /// <param name="data"></param>
        /// <returns></returns>
        public bool Remove(T key, int data)
        {
            Node<T> find = search(root, key);
            if (find == null || !find.data.Contains(data))
                return false;
            else
            {
                find.data.Remove(data);
                return true;
            }
        }
        /// <summary>
        /// 修改节点
        /// </summary>
        /// <param name="oldKey"></param>
        /// <param name="newKey"></param>
        /// <param name="data"></param>
        /// <returns></returns>
        public bool Update(T oldKey, T newKey, int data)
        {
            Node<T> oldNode = search(root, oldKey);
            if (oldNode == null) return false;
            if (oldNode != null && oldNode.data.Contains(data))
            {
                oldNode.data.Remove(data);
                //return true;
            }
            Add(newKey, data);
            return true;
        }

        public void show()
        {
            show(root);
        }


        private bool tless(Node<T> x, Node<T> y)
        {
            return x.key.CompareTo(y.key) < 0;
        }
        /// <summary>
        /// 创建一个新节点
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        private Node<T> new_node(T key)
        {
            Node<T> p = new Node<T>();
            p.left = p.right = null;
            p.key = key;
            p.data = new ConcurrentHashSet<int>();
            p.rank = rand.Next();
            return p;
        }
        /// <summary>
        /// 右旋
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        private Node<T> turn_right(Node<T> t)
        {
            Node<T> p = new Node<T>();
            p = t.left;
            t.left = p.right;
            p.right = t;
            return p;
        }
        /// <summary>
        /// 左旋
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        private Node<T> turn_left(Node<T> t)
        {
            Node<T> p = new Node<T>();
            p = t.right;
            t.right = p.left;
            p.left = t;
            return p;
        }

        private Node<T> insert(Node<T> t, Node<T> u)
        {
            if (t == null) return u;
            if (tless(u, t))
            {
                t.left = insert(t.left, u);
                if (t.left.rank > t.rank) return turn_right(t);
            }
            else
            {
                t.right = insert(t.right, u);
                if (t.right.rank > t.rank) return turn_left(t);
            }
            return t;
        }

        private Node<T> merge(Node<T> x, Node<T> y)
        {
            if (x == null) return y;
            if (y == null) return x;
            if (x.rank < y.rank)
            {
                x.right = merge(x.right, y);
                return x;
            }
            else
            {
                y.left = merge(x, y.left);
                return y;
            }
        }

        private Node<T> erase(Node<T> t, Node<T> u)
        {
            if (t == null) return null;
            if (t == u)
            {
                return merge(t.left, t.right);
            }
            else
            {
                if (tless(u, t))
                    t.left = erase(t.left, u);
                else
                    t.right = erase(t.right, u);
            }
            return t;
        }

        private Node<T> search(Node<T> t, T key)
        {
            if (t == null) return null;
            switch (key.CompareTo(t.key))
            {
                case -1:
                    return search(t.left, key);
                case 0:
                    return t;
                case 1:
                    return search(t.right, key);
            }
            return t;
        }

        private void show(Node<T> t)
        {
            if (t == null) return;
            show(t.left);
            Console.WriteLine(t.key);
            foreach (int x in t.data)
            {
                Console.Write("{0} ", x);
            }
            Console.WriteLine();
            show(t.right);
        }
        // Node<T>

        /// <summary>
        /// 中序遍历儿叉树
        /// </summary>
        /// <param name="node">根节点</param>
        /// <param name="way">排序方式,desc为降序，asc为升序</param>
        /// <param name="nodeList">排序结果集</param>
        /// <returns></returns>
        public void MidOrder(Node<T> node, string way, ref List<HashSet<int>> nodeList)
        {
            
            if (node != null)
            {
                Node<T> cur = node;
                Node<T> begin = node.left;
                Node<T> end = node.right;
                if (way.ToLower() == "desc")
                {
                    begin = node.right;
                    end = node.left;
                }
                 MidOrder(begin, way, ref nodeList);
                if (cur.data != null)
                {
                    HashSet<int> hash = new HashSet<int>();
                    hash.UnionWith(cur.data);
                    nodeList.Add(hash);
                }
                 MidOrder(end, way, ref nodeList);
            }

            //if (node == null)
            //    return;

            //MidOrder(node.left, way, ref  nodeList);
            //if (node.data != null)
            //{
            //    HashSet<int> hash = new HashSet<int>();
            //    hash.UnionWith(node.data);
            //    nodeList.Add(hash);
            //}
            //MidOrder(node.right, way, ref  nodeList);
        }
        /// <summary>
        /// 获取排序二叉树所有节点
        /// </summary>
        /// <param name="way">排序方式，asc为升序，desc为降序</param>
        /// <returns></returns>
        public List<HashSet<int>> OrderByBinaryTree(string way)
        {
            if (string.IsNullOrEmpty(way)) 
                throw new ArgumentNullException("way(排序方式,升序或降序)");
            List<HashSet<int>> list = new List<HashSet<int>>();
            MidOrder(root, way, ref list);
            return list;
        }
        /// <summary>
        /// 大于key
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        private List<Node<T>> GreaterThan(T key, bool isEqual)
        {
            Stack<Node<T>> workStack = new Stack<Node<T>>();
            List<Node<T>> list = new List<Node<T>>();
            if (root != null)
            {
                workStack.Push(root);
                list.Add(root);
            }
            while (workStack.Count != 0)
            {
                Node<T> node = workStack.Pop();
                //list.Add(node);
                //if (node.left != null)
                //    workStack.Push(node.left);
                //if (node.right != null)
                //    workStack.Push(node.right);
                if (node.key.CompareTo(key) == 1)
                {
                    //list.Add(node);
                    if (node.left != null)
                    {
                        workStack.Push(node.left);
                        list.Add(node.left);
                    }
                    if (node.right != null)
                    {
                        workStack.Push(node.right);
                        list.Add(node.right);
                    }
                }
                else if (node.key.CompareTo(key) == -1)
                {
                    if (node.right != null)
                    {
                        workStack.Push(node.right);
                        list.Add(node.right);
                    }
                }
                else if (node.key.CompareTo(key) == 0)
                {
                    if (node.right != null)
                    {
                        workStack.Push(node.right);
                        list.Add(node.right);
                    }
                }
            }

            list = list.FindAll(delegate(Node<T> n)
            {
                if (isEqual)
                    return n.key.CompareTo(key) == 1 || n.key.CompareTo(key) == 0;
                return n.key.CompareTo(key) == 1;
            });
            return list;
        }
        /// <summary>
        /// 小于key
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        private List<Node<T>> LessThan(T key, bool isEqual)
        {
            Stack<Node<T>> lworkStack = new Stack<Node<T>>();

            List<Node<T>> list = new List<Node<T>>();
            if (root != null)
            {
                lworkStack.Push(root);
                list.Add(root);
            }

            while (lworkStack.Count != 0)
            {
                Node<T> node = lworkStack.Pop();
                if (node.key.CompareTo(key) == -1)
                {
                    if (node.left != null)
                    {
                        list.Add(node.left);
                        lworkStack.Push(node.left);
                    }
                    if (node.right != null)
                    {
                        list.Add(node.right);
                        lworkStack.Push(node.right);
                    }
                }
                else if (node.key.CompareTo(key) == 1)
                {
                    if (node.left != null)
                    {
                        list.Add(node.left);
                        lworkStack.Push(node.left);
                    }
                }
                else if (node.key.CompareTo(key) == 0)
                {
                    if (node.left != null)
                    {
                        lworkStack.Push(node.left);
                        list.Add(node.left);
                    }
                }
            }
            list = list.FindAll(delegate(Node<T> n)
            {
                if (isEqual)
                    return n.key.CompareTo(key) == -1 || n.key.CompareTo(key) == 0;
                return n.key.CompareTo(key) == -1;
            });
            return list;
        }
        /// <summary>
        /// 区间查询
        /// </summary>
        /// <param name="min"></param>
        /// <param name="max"></param>
        /// <param name="hasIncludeMin"></param>
        /// <param name="hasIncludeMax"></param>
        /// <returns></returns>
        private List<Node<T>> RegionQuery(T min, T max, bool hasIncludeMin, bool hasIncludeMax)
        {
            Stack<Node<T>> rworkStack = new Stack<Node<T>>();

            List<Node<T>> list = new List<Node<T>>();
            if (root != null)
            {
                rworkStack.Push(root);
                list.Add(root);
            }

            while (rworkStack.Count != 0)
            {
                Node<T> curNode = rworkStack.Pop();
                if (curNode.key.CompareTo(min) == -1 || curNode.key.CompareTo(min) == 0)
                {
                    if (curNode.right != null)
                    {
                        list.Add(curNode.right);
                        rworkStack.Push(curNode.right);
                    }
                }
                else if (curNode.key.CompareTo(max) == 1 || curNode.key.CompareTo(max) == 0)
                {
                    if (curNode.left != null)
                    {
                        list.Add(curNode.left);
                        rworkStack.Push(curNode.left);
                    }
                }
                else if (curNode.key.CompareTo(min) == 1 && curNode.key.CompareTo(max) == -1)
                {
                    if (curNode.left != null)
                    {
                        list.Add(curNode.left);
                        rworkStack.Push(curNode.left);
                    }
                    if (curNode.right != null)
                    {
                        list.Add(curNode.right);
                        rworkStack.Push(curNode.right);
                    }
                }

            }
            list = list.FindAll(delegate(Node<T> n)
            {
                if (hasIncludeMin && hasIncludeMax)
                    return ((n.key.CompareTo(min) == 1 || n.key.CompareTo(min) == 0) && (n.key.CompareTo(max) == -1 || n.key.CompareTo(max) == 0));
                else if (hasIncludeMax)
                    return (n.key.CompareTo(min) == 1 && (n.key.CompareTo(max) == -1 || n.key.CompareTo(max) == 0));
                else if (hasIncludeMin)
                    return ((n.key.CompareTo(min) == 1 || n.key.CompareTo(min) == 0) && n.key.CompareTo(max) == -1);

                return n.key.CompareTo(min) == 1 && n.key.CompareTo(max) == -1;
            });
            return list;
        }
        /// <summary>
        /// 大于、大于等于、小于、小于等于、等于
        /// </summary>
        /// <param name="node"></param>
        /// <param name="key"></param>
        /// <returns></returns>
        public HashSet<int> Find(T key, EnumOperation operation)
        {
            List<Node<T>> list = new List<Node<T>>();
            HashSet<int> result = new HashSet<int>();
            List<int> list2 = new List<int>();
            switch (operation)
            {
                case EnumOperation.GreaterThan:
                    list = GreaterThan(key, false);
                    break;
                case EnumOperation.GreaterThanEqual:
                    list = GreaterThan(key, true);
                    break;
                case EnumOperation.LessThan:
                    list = LessThan(key, false);
                    break;
                case EnumOperation.LessThanEqual:
                    list = LessThan(key, true);
                    break;
                case EnumOperation.Equal:
                    Node<T> node = search(root, key);
                    if (node != null)
                        result.UnionWith(node.data);
                    break;
            }
            //try
            //{
            foreach (Node<T> item in list)
            {
                result.UnionWith(item.data);
            }
            //}
            //catch (Exception e) { Find(key, operation); }

            return result;
        }

        /// <summary>
        /// 区间查找
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <param name="operation"></param>
        /// <returns></returns>
        public HashSet<int> Find(T min, T max, EnumOperation operation)
        {
            List<Node<T>> list = new List<Node<T>>();
            HashSet<int> result = new HashSet<int>();
            switch (operation)
            {
                case EnumOperation.RightClosedLeftClosed:
                    list = RegionQuery(min, max, true, true);
                    break;
                case EnumOperation.RightOpenLeftOpen:
                    list = RegionQuery(min, max, false, false);
                    break;
                case EnumOperation.RightOpenLeftClosed:
                    list = RegionQuery(min, max, true, false);
                    break;
                case EnumOperation.RightClosedLeftOpen:
                    list = RegionQuery(min, max, false, true);
                    break;
            }
            //try
            //{
            foreach (Node<T> item in list)
            {
                result.UnionWith(item.data);
            }
            //}
            //catch (Exception e) { Find(min, max, operation); }
            return result;
        }
    }
    public class Node<T>
    {
        public T key;
        public int rank;
        public ConcurrentHashSet<int> data;
        public Node<T> left, right;
    }
}